package liangtWorkSpace.leetcode;

/**
 * @ClassName LeetCode
 * @Description : 功能说明
 * @Author : LiangT
 * @Date : 2020/4/20 11:05
 */

/**
 * 获取最大公约数
 */
public class LeetCode {
    /**
     * 二者结合
     */
    public static int gcd(int a,int b){
        if (a == b){
            return a;
        }
        if ((a&1) == 0 && (b&1) == 0){
            return gcd(a>>1 ,b >>1);
        }else if ((a&1) == 0 && (b&1) != 0){
            return gcd(a>>1,b);
        }else if ((a&1) != 0 && (b&1) == 0){
            return gcd(a,b>>1);
        }else {
            int big = a>b? a:b;
            int small = a < b? a:b;
            return gcd(big - small,small);
        }
    }

    public static void main(String[] args) {
        System.out.println(gcd(25, 5));
        System.out.println(gcd(100, 80));
        System.out.println(gcd(27, 14));
    }
}

/**
 * 更相减损法
 *
 */
class GreatesCommonDivisor2{
    /**
     *更相减损法
     * @param a
     * @param b
     * @return
     */
    public static int getGreatesCommonDivisor(int a,int b){


        if (a == b){
            return a;
        }
        int big = a>b? a:b;
        int small = a < b ? a:b;
        return getGreatesCommonDivisor(big-small,small);
    }

    public static void main(String[] args) {
        System.out.println(getGreatesCommonDivisor(25, 5));
        System.out.println(getGreatesCommonDivisor(100, 80));
        System.out.println(getGreatesCommonDivisor(27, 14));

    }
}
/**
 * 辗转相除法
 * 计算出a除以b的余数c，把问题转化成求b和c的最大公约数；
 * 然后计算出b除以c的余数d，把问题转化成求c和d的最大公约数；
 * 再计算 出c除以d的余数e，把问题转化成求d和e的最大公约数……
 */
class GreatesCommonDivisor{
    /**
     *辗转相除法
     * @param a
     * @param b
     * @return
     */
    public static int getGreatesCommonDivisor(int a,int b){
        int big = a>b? a:b;
        int small = a < b ? a:b;

        if (big%small == 0){
            return small;
        }
        return getGreatesCommonDivisor(big%small,small);
    }

    public static void main(String[] args) {
        System.out.println(getGreatesCommonDivisor(25, 5));
        System.out.println(getGreatesCommonDivisor(100, 80));
        System.out.println(getGreatesCommonDivisor(27, 14));

    }
}
